/**
 * https://leetcode-cn.com/problems/longest-common-subsequence/
 * 最长公共子序列
 * @param text1 
 * @param text2 
 */
const longestCommonSubsequence = (text1: string, text2: string): number => {
    const t1Len = text1.length,
        t2Len = text2.length;
    const dp: number[] = new Array(t2Len + 1).fill(0)

    // 两层for循环, 把所有的字符串都考虑在内
    for (let i = 1; i <= t1Len; i++) {
        let cur = 0 // 默认是第一项, 都是0
        for (let j = 1; j <= t2Len; j++) { // 给dp行添加
            // 获取上一个左上角的值
            let leftTop = cur
            // 保存当前的值
            cur = dp[j]
            if (text1[i - 1] !== text2[j - 1]) {
                // 不相等
                dp[j] = Math.max(dp[j - 1], dp[j])
            } else {
                // 相等
                dp[j] = leftTop + 1
            }
        }
    }
    return dp[t2Len]
};



// 二维数组
const longestCommonSubsequence3 = (text1: string, text2: string): number => {

    // abcde
    // ace
    // dp[0] = 0 

    // dp(i, j) 表示以i为底, j为底的最长公共子序列

    // 状态转移方程
    // if (t1[k] === t2[k]) dp[i, j] = dp[i - 1, j - 1] + 1
    // else {
    //     dp[i, j] = max {
    //         dp[i - 1, j],
    //             dp[i, j - 1]
    //     }
    // }
    const t1Len = text1.length,
        t2Len = text2.length;
    const dp: number[][] = new Array(t1Len + 1)

    for (let i = 0; i < dp.length; i++) {
        dp[i] = new Array(t2Len + 1).fill(0)
    }

    // 两层for循环, 把所有的字符串都考虑在内
    for (let i = 1; i <= t1Len; i++) {
        for (let j = 1; j <= t2Len; j++) {
            if (text1[i - 1] !== text2[j - 1]) {
                // 不相等
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])
            } else {
                // 相等
                dp[i][j] = dp[i - 1][j - 1] + 1
            }
        }
    }
    return dp[t1Len][t2Len]
};

longestCommonSubsequence('abcba', 'abcbcba')

// 暴力递归, 超出时间限制
const longestCommonSubsequence2 = (text1: string, text2: string): number => {
    // abcde
    // ace
    const lcs = (i: number, j: number): number => {
        // 边界判断
        if (i === 0 || j === 0) return 0;

        // 两个不相等
        if (text1[i] !== text2[i]) {
            return Math.max(lcs(i - 1, j), lcs(i, j - 1))
        }

        // 两个元素当前位置相等
        return lcs(i - 1, j - 1) + 1
    }

    return lcs(text1.length, text2.length)
};